#include <stdio.h>
#include <stdlib.h>
#include "fila.h"

/* monta uma lista ordenada com 256 listas simples com no cabeca */
ListaSimples *(MontaListaOrdenada(void))
{
	ListaOrdenada *posicao;
	int i;

	posicao = malloc(256 * sizeof(ListaOrdenada));

	for (i = 0;i < 256;i++)
		posicao[i] = NULL;
	
	for (i = 0;i < 256;i++)
	{
		InsereListaSimples(&posicao[i],-1,-1);
	}

	return (ListaOrdenada)posicao;
}

/* Libera somente a lista simples, inclusive o no cabeca, para verificar se a lista da prioridade
foi fechada */
void LiberaListaSimples(ListaSimples **inicio)
{
	ListaSimples *lixo,*aux;
	if (*inicio == NULL)
		return;	
	lixo = (*inicio);
	aux = lixo;
	while (lixo != NULL)
	{
		aux = aux->prox;
		free(lixo);
		lixo = aux;
	}
	*inicio = NULL;
	return;
}

/* !!! essa funcao eh soh pra teste, pra ver se tah colocando certo na fila ordenada, depois tem q tirar !!! */
void imprime(ListaOrdenada *p)
{
	int i;
	ListaOrdenada aux;

	for (i = 0;i < 256;i++)
	{
		aux = p[i];
		while (aux != NULL)
		{
			printf("%d - %d %d\n",i,aux->indice,aux->prioridade);
			aux = aux->prox;
		}
	}
	return;
}


/* libera todas as listas simples da lista ordenada e o vetor de ponteiros */
void LiberaListaOrdenada(ListaSimples **vet)
{
	int i;

	for (i = 0;i < 256;i++)
	{
		LiberaListaSimples(&vet[i]);
	}

	free(vet);

	return;
}
/* insere um elemento no final da lista simples */
void InsereListaSimples(ListaSimples **inicio,int indice,int prioridade)
{
	ListaSimples *aux,*novo;
	
	novo = (ListaSimples *)malloc(sizeof(ListaSimples));
	
	novo->indice = indice;
	novo->prioridade = prioridade;
	novo->prox = NULL;
	aux = (*inicio);
	if (aux != NULL)
	{
		while (aux->prox != NULL)
			aux = aux->prox;
		aux->prox = novo;
	}
	else
		*inicio = novo;
	return;
}

/* insere um elemento na lista de prioridade escolhida ou se nao for possivel, na proxima lista aberta de menor prioridade */
ListaSimples* (InsereListaOrdenada(ListaSimples **lista,int prioridade,int indice, Imagem *img))
{
	int i;
	int lin,col;
	
	lin = (indice/(img)->ncols);
	col = (indice%(img)->ncols);
	
	if (!pixel_valido(img,col,lin))
		return *lista;
	
	/* inicia o indice a partir da prioridade escolhida */
	i = prioridade;
	
	/* verifica se as prioridades a partir da escolhida ja foram fechadas */
	while (lista[i] == NULL && i < 256)
		i++;
	
	/* adiciona a prioridade escolhida ou a mais proxima, o elemento na prioridade */
	if (i < 256)
		InsereListaSimples(&lista[i],indice,prioridade);

	return *lista;
}

/* tira o elemento de maior prioridade e que chegou primeiro na fila ordenada e retorna o endereco */
ListaSimples* (TiraElemento(ListaSimples **lista))
{
	int i = 0;
	ListaSimples *aux = NULL;
	
	while (lista[i] == NULL && i < 256)
		i++;

	if (i < 256)
	{
		aux = lista[i];
		if (aux != NULL)
		{
			aux = aux->prox;
			lista[i]->prox = aux->prox;
		}
	}

	return aux;
}

/* funcao recursiva que adiciona os marcadores iniciais na fila ordenada */
void IniciaFila(Imagem *img, Imagem *rotulo, ListaSimples **inicio, int comeco)
{
	int n;

	n = (rotulo)->ncols * (rotulo)->nlins;
	if (comeco < n)
	{
		if ((rotulo)->val[comeco] != 0)
			InsereListaOrdenada(inicio,(img)->val[comeco],comeco,img);
		IniciaFila(img,rotulo,inicio,comeco + 1);
	}
}



